package com.exercise;

public class MinSum {


    static int count = 0;
    /**
     * 找到 给定n个数  用m个加号分割时的最小值
     * @param input
     */
    public static int findMinSum(int[] input, int m){
        //存储每个n在m下的最小值。
        int n = input.length;
        int[][] minArray = new int[n][m];
        for(int i = 0;i < n;i ++){
            for(int j = 0;j < m;j ++){
                minArray[i][j] = -1;
            }
        }
        return findMinSumInner(input,n, m,minArray);


    }

    private static int findMinSumInner(int[] input, int n, int m,int[][] minArray) {

        count ++;
        if(m >= n){
            minArray[n - 1][m - 1] = 9999999;
            return 9999999;
        }
        if(n <= 1){
            return input[n - 1];
        }
        if(m <= 0){
            return sum(input,0,n - 1);
        }


        int min = 9999999;
        for(int i = n - 1; i >= m; i --){
            int tmp;

            if(m - 2 >= 0) {
                if ((tmp = minArray[i - 1][m - 2]) != -1) {
                    tmp += sum(input,i,n - 1);
                    if (tmp < min) {
                        min = tmp;
                    }
                    continue;
                }
            }

            tmp = findMinSumInner(input,i,m - 1,minArray);
            tmp += sum(input,i,n - 1);
            if(tmp < min){
                min = tmp;
            }
        }
        minArray[n - 1][m - 1] = min;
        System.out.println(n+"个数"+m+"个加号"+"最小值为"+min);
        return min;
    }

    private static int sum(int[] input,int start,int end) {
        int sum = 0;
        for(int i = start; i <= end;i ++){
            sum += input[i] * Math.pow(10,end - i);
        }
        return sum;
    }



    public static void main(String[] args){
        int allCount = 11;
        int[] a = new int[allCount];

        for(int i = 0;i < allCount;i ++){
            a[i] = i + 1;
        }

        long before = System.currentTimeMillis();

        int res = findMinSum(a,1);

        long after = System.currentTimeMillis();

        System.out.println(after - before);

        System.out.println(res);

        System.out.println(count);
    }
}
